package sword.offer;

import java.util.HashSet;
import java.util.Set;

/**
 * 输入两个链表，找出它们的第一个公共节点。
 *
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FiftyTwo {

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            Set<ListNode> set = new HashSet<>();
            ListNode resNode = headA;
            while(resNode!=null){
                set.add(resNode);
                resNode = resNode.next;
            }

            while(headB!=null){
                if(set.contains(headB)){
                    return headB;
                }
                headB = headB.next;
            }
            return null;
        }
    }


    /**
     * <b>这个题解实在是太妙了 简直了！！！！</b><br/>
     *
     * 我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点<br />
     * 然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；<br />
     * 当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
     * <p>这样，当它们相遇时，所指向的结点就是第一个公共结点</p>
     * https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/shuang-zhi-zhen-fa-lang-man-xiang-yu-by-ml-zimingm/
     * */
    public class Solution1 {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode l1 = headA;
            ListNode l2 = headB;
            // 当两个指针都指向null 即两个链表都遍历完了 且在尾结点的next相遇了 null!=null退出循环。
            while (l1 != l2){
                // 我走过你走过的路
                l1 = l1 == null ? headB : l1.next;
                // 你吹过我吹过的风
                l2 = l2 == null ? headA : l2.next;
            }
            // 这样我们才能相拥
            return l1;
        }
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
